package array;

import java.util.Arrays;

/**
 * @author yuisama
 * @date 2022/08/25 09:10
 **/
public class ArrayHomeWork {
    public static void main(String[] args) {
//        int[] arr = {2,7,11,15};
//        int[] ret = twoSum(arr,9);
//        System.out.println(Arrays.toString(ret));
//        int[] arr1 = {2,6,4,1};
//        int[] arr2 = {1,2,34,3,4,5,6,7,23,12};
//        System.out.println(isConsecutiveOdds(arr1));
//        System.out.println(isConsecutiveOdds(arr2));
//        int[] arr1 = {2,2,1};
//        int[] arr2 = {4,1,2,1,2};
//        System.out.println(singleNum(arr1));
//        System.out.println(singleNum(arr2));
        int[] arr1 = {3,2,3};
        int[] arr2 = {2,2,1,1,1,2,2};
        System.out.println(manyNumVote(arr1));
        System.out.println(manyNumVote(arr2));
    }
    // 摩尔投票法,O(N) 专门解决众数问题
    public static int manyNumVote(int[] arr) {
        // 用count记录赞成者人数
        int count = 0;
        int candidate = -1;
        for (int i : arr) {
            if (count == 0) {
                // 更换候选人为当前的数
                candidate = i;
            }
            if (i != candidate) {
                // 投反对票
                count --;
            }else {
                // 投赞成票
                count ++;
            }
        }
        // 最终淘汰下来剩下的候选人一定是众数
        return candidate;
    }

    // 5.众数问题
    // 排序法 O(nlogn)
    public static int manyNum(int[] arr) {
        // 排序
        Arrays.sort(arr);
        return arr[arr.length / 2];
    }


    // 4.只出现一次的数字
    // 前提 : 这个数组arr中，有且只有一个元素出现一次，其他所有元素均出现两次
    public static int singleNum(int[] arr) {
        int ret = 0;
        for(int i : arr) {
            // ret = ret ^ i;
            ret ^= i;
        }
        return ret;
    }

    // 3.判断数组中是否包含连续的三个奇数
    public static boolean isConsecutiveOdds(int[] nums) {
        // 引入变量，存储连续出现的奇数的个数
        int oddCount = 0;
        for (int i : nums) {
            if (i % 2 != 0) {
                // 是个奇数
                oddCount ++;
            }else {
                // 此时碰到偶数，计数器还原！
                // 重置计数器
                oddCount = 0;
            }
            if (oddCount == 3) {
                return true;
            }
        }
        return false;
    }


    // 2.两数之和
    public static int[] twoSum(int[] arr,int target) {
        int[] ret = new int[2];
        outter:
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[i] + arr[j] == target) {
                    // 找到解
                    ret[0] = i;
                    ret[1] = j;
                    break outter;
                }
            }
        }
        return ret;
    }
    // 1.调整数组顺序，奇数在偶数之前
    // 原数组 [1,2,3,4,5,6] => [1,5,3,4,2,6]
    public static void swapArr(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        // 当left >= right循环终止
        while (left < right) {
            // left从前向后寻找第一个偶数停止
            // 为何在内层循环找奇数和偶数时，仍然需要判断终止条件？不写行不行？
            while (left < right && arr[left] % 2 != 0) {
                left ++;
            }
            // right从后向前寻找第一个奇数停止
            while (left < right && arr[right] % 2 == 0) {
                right --;
            }
            // 当这两个循环都退出时，只可能有两种情况 :
            // 1.left指向第一个偶数，right指向第一个奇数
            // 2.left或right走到头或相等了.只剩一个元素
            // left就指向第一个偶数，right就指向了第一个奇数，交换他俩的元素
            swap(arr,left++,right--);
//            left ++;
//            right --;
        }
    }



    public static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}